/*-
 * Copyright 2012 Matthew Endsley
 * All rights reserved
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted providing that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef TINYSTL_STRING_H
#define TINYSTL_STRING_H

#include "bx/string.h"
#include "hash.h"
#include "stddef.h"
#include "vector.h"
#include <assert.h>
#include <ctype.h>
#include <math.h>
#include <ostream>
#include <stdio.h>
#include <string.h> // strlen
#include <utility>

namespace {
inline bool isValidDigit(char digit, int base) {
  // If base is 0, use 10 as the numberical base
  base = base == 0 ? 10 : base;
  int step = base - 1;

  if (base >= 2 && base <= 10) {
    return digit >= '0' && digit <= '0' + step;
  }

  if (base > 10 && base <= 36) {
    step = base - 10;
    return (digit >= '0' && digit <= '9') ||
           (digit >= 'a' && digit <= 'a' + step);
  }
  return false;
}
} // namespace

namespace tinystl {

typedef unsigned int usize;
static const int npos = -1;

namespace util {

template <typename T> int find(const T &str, char ch, usize pos) {
  for (usize i = pos; i < str.size(); i++) {
    if (str.data()[i] == ch)
      return i;
  }
  return npos;
}

template <typename U, typename V>
int find(const U &str, const V &findit, usize pos = 0) {
  bx::StringView srcView(str.data() + pos, str.size() - pos);
  bx::StringView fView(findit.data(), findit.size());
  auto ret = bx::strFind(srcView, fView);
  if (ret.isEmpty())
    return npos;
  return ret.getPtr() - str.data();
}

} // namespace util

template <typename Alloc> class stringT {
public:
  typedef int size_type;
  typedef stringT<Alloc> this_type;
  static const int npos = -1;

  class stringview {
  public:
    stringview() = default;
    stringview(const char *literal) {
      m_first = literal;
      m_size = strlen(m_first);
    }

    stringview(const char *literal, usize sz) {
      m_first = literal;
      m_size = sz;
    }

    // 这个函数返回的地址不能代表字符串，它没有字符串的\0结尾
    // 不要直接用于const char* 传递
    inline const char *data() const { return m_first; }
    inline usize size() const { return m_size; }
    inline bool empty() const { return m_size == 0; }

    char operator[](usize i) const { return m_first[i]; }

    //    operator stringT<Alloc>() const {
    //      stringT<Alloc> ret(*this);
    //      return std::move(ret);
    //    }

    stringT<Alloc> toStr() const {
      stringT<Alloc> ret(*this);
      return std::move(ret);
    }

    inline int find(const stringview &str) const {
      return util::find(*this, str);
    }

    int find(const stringview &str, usize pos) const {
      return util::find(*this, str, pos);
    }

    int find(char ch, usize pos = 0) const {
      return util::find(*this, ch, pos);
    }

    int find_first_of(const stringview &str, usize pos = 0) const {
      for (usize i = pos; i < size(); i++) {
        char ch = (*this)[i];
        if (str.find(ch) != npos)
          return i;
      }
      return npos;
    }

    stringview substr(usize from, int len = -1) const {
      if (from >= size())
        return stringview();
      if (len < 0 || from + len > size())
        len = (int)(size() - from);
      return stringview(data() + from, len);
    }

    bool beginWith(const stringview &sv) const {
      if (sv.size() > size())
        return false;
      for (usize i = 0; i < sv.size(); i++) {
        if ((*this)[i] != sv[i])
          return false;
      }
      return true;
    }

    stringview trim(char what = 0) const {
      if (size() == 0) {
        return stringview();
      }

      what = what == 0 ? ' ' : what;

      usize begPos = 0;
      const char *chr = m_first;
      for (; chr != m_first + m_size; chr++) {
        if (*chr != what && *chr != '\t' && *chr != '\n' && *chr != '\r') {
          break;
        }
        begPos++;
      }

      if (chr == m_first + m_size) {
        return stringview();
      }

      usize endPos = size();
      for (chr = m_first + m_size - 1; chr != m_first; chr--) {
        if (*chr != what && *chr != '\t' && *chr != '\n' && *chr != '\r') {
          break;
        }
        endPos--;
      }

      return substr(begPos, (int)(endPos - begPos));
    }

    int toInt() const {
      int ret = 0;
      bx::fromString(&ret, bx::StringView(data(), (int)m_size));
      return ret;
    }

    float toFloat() const {
      float ret = NAN;
      if (bx::fromString(&ret, bx::StringView(data(), (int)m_size)))
        return ret;
      return NAN;
    }

    bool operator==(const stringview &str) const {
      usize min = bx::min(size(), str.size());
      return strncmp(data(), str.data(), min) == 0;
    }

    bool operator==(const char *str) const {
      usize min = bx::min(size(), (usize)strlen(str));
      return strncmp(data(), str, min) == 0;
    }

    // siney
    friend stringT<Alloc> operator+(const stringview &lhs,
                                    const stringview &rhs) {
      stringT<Alloc> ret(lhs);
      ret.append(rhs);
      return std::move(ret);
    }

    template <typename E, typename T>
    friend std::basic_ostream<E, T> &
    operator<<(std::basic_ostream<E, T> &output,
               const typename stringT<Alloc>::stringview &c) {
      output.write(c.data(), c.size());
      return output;
    }

  protected:
    const char *m_first;
    usize m_size;
  };

  stringT();

  stringT(const stringT<Alloc> &other);

  stringT(stringT<Alloc> &&other);

  stringT(const char *sz);

  stringT(const stringview &sv) : stringT(sv.data(), sv.size()) {}

  stringT(const char *sz, usize len);

  stringT(const bx::StringView &view);

  ~stringT();

  stringT<Alloc> &operator=(const stringT<Alloc> &other);

  // siney
  stringT<Alloc> &operator=(stringT<Alloc> &&other);

  const char *c_str() const;
  inline const char *data() const { return c_str(); }

  usize size() const;

  inline usize length() const { return size(); }

  inline usize capacity() const { return m_capacity; }

  bool empty() const;

  void reserve(usize _size);

  void resize(usize _size);

  // siney
  void set(const char *str, usize len);

  void append(const char *first, const char *last);

  void append(const char *str, usize len = 0);

  void insert(size_t pos, const char *str);

  inline void append(char ch) { append(&ch, 1); }

  inline void append(const stringview &sv) { append(sv.data(), sv.size()); }

  inline void append(const stringT<Alloc> &str) {
    append(str.c_str(), str.size());
  }

  inline void push_back(char ch) { append(ch); }

  // void swap(stringT<Alloc>& other);

  inline operator const char *() const { return c_str(); }

  inline char operator[](int i) const { return c_str()[i]; }

  inline char at(int i) const { return c_str()[i]; }

  static stringT<Alloc> format(const char *msg, ...);

  // 返回stringview
  inline stringview slice(usize from = 0, usize len = -1) const {
    return substr(from, len);
  }

  // siney
  inline int find(const stringview &str) const {
    return util::find(*this, str);
  }

  inline int find(const stringview &str, usize pos) const {
    return util::find(*this, str, pos);
  }

  inline int find(char ch, usize pos = 0) const {
    return util::find(*this, ch, pos);
  }

  // find reverse
  inline int findLast(char ch) const {
    const char *p = strrchr(c_str(), ch);
    if (!p)
      return -1;
    return (int)(p - c_str());
  }

  // find reverse
  int findLast(const stringT<Alloc> &str) const;

  // fint first not of
  int findNot(const stringT<Alloc> &str, usize pos = 0) const;

  int find_first_of(const stringview &str, usize pos = 0) const {
    return slice().find_first_of(str, pos);
  }

  int find_first_of(char ch, usize pos = 0) const {
    for (usize i = pos; i < size(); i++) {
      char chi = at(i);
      if (chi == ch)
        return i;
    }
    return npos;
  }

  int find_first_not_of(const stringT<Alloc> &str, usize pos = 0) const {
    for (usize i = pos; i < size(); i++) {
      char ch = at(i);
      if (str.find(ch) == npos)
        return i;
    }
    return npos;
  }

  int find_last_of(const stringT<Alloc> &str) const {
    for (int i = (int)size() - 1; i >= 0; i--) {
      char ch = at(i);
      if (str.find(ch) != npos)
        return i;
    }
    return npos;
  }

  inline int find_last_of(char ch) const {
    for (int i = (int)size() - 1; i >= 0; i--) {
      char chi = at(i);
      if (chi == ch)
        return i;
    }
    return npos;
  }

  void erase(const char *from, const char *to = nullptr) {
    if (from < c_str() || from > c_str() + size())
      return;

    if (to)
      *this = substr(0, from - c_str()) + substr(to - c_str());
    else
      *this = substr(0, from - c_str()) + substr(from - c_str() + 1);
  }

  void erase(size_type from, size_type len = -1) {
    if (from < 0 || from > (int)size())
      return;

    if (len >= 0)
      *this = substr(0, from) + substr(from + len);
    else
      *this = substr(0, from);
  }

  // siney
  inline stringT<Alloc> left(usize len) const { return substr(0, (int)len); }

  // siney
  inline stringT<Alloc> mid(usize pos, int len = -1) const {
    return substr(pos, len);
  }

  // siney
  bool beginWith(const stringT<Alloc> &prefix) const;

  bool endWith(const stringT<Alloc> &prefix) const;

  void lower();

  void upper();

  const char *begin() const {
    if (size() > 0)
      return c_str();
    return nullptr;
  }

  const char *end() const { return m_first + m_size; }

  /*
   * @author: glosimarsun
   * @return: the string coverted to uppercase,
   *          but not change the original string.
   */
  stringT<Alloc> toUpperCase();

  /*
   * @author: glosimarsun
   * @return: the string coverted to lowercase,
   *          but not change the original string.
   */
  stringT<Alloc> toLowerCase();

  // siney
  stringview substr(usize from, int len = -1) const;

  // siney
  stringT<Alloc> operator+(const stringT<Alloc> &rhs) const;

  stringT<Alloc> operator+(char c) const {
    stringT<Alloc> ret(*this);
    ret.append(c);
    return ret;
  }

  /***
   * Convert integer to string
   * @param num Value to be converted to a string.
   * @param radix Numerical base used to represent the value as a string,
   *              between 2 and 36. If base is 0, use 10 as the numberical base
   * @return the converted string or just empty
   */
  static stringT<Alloc> itos(int value, int base = 10);

  /***
   * Convert string to integer
   * @param str String object with the representation of an integral number.
   * @param idx Pointer to an object of type usize,
   *            whose value is set by the function to position of
   *            the next character in str after the numerical value.
   *            This parameter can also be a null pointer, in which case it is
   * not used. e.g. stoi("123sss", idxPtr, 10) -> return 123, and idxPtr equals
   * 3
   * @param base Numerical base (radix) that determines the valid characters and
   * their interpretation. If base is 0, use 10 as the numberical base
   * @return the converted integral number as an int value.
   */
  static int stoi(const stringT<Alloc> &str, usize *idx = 0, int base = 10);

  int toInteger(int base = 10) const { return atoi(c_str()); }
  int toFloat() const { return atof(c_str()); }

  // concat 2 path
  stringT<Alloc> operator/(const stringT<Alloc> &rhs) const;

  stringT<Alloc> operator/(const stringview &rhs) const {
    stringT<Alloc> ret(*this);
    ret.pathConcat(rhs);
    return std::move(ret);
  }

  void pathConcat(const stringT<Alloc> &rhs);
  void pathConcat(const stringview &rhs);

  // siney
  void operator+=(const stringT<Alloc> &rhs);

  inline void operator+=(const char c) { this->append(c); };

  void replace(char t, char r);

  stringT<Alloc> replace(const this_type &from, const this_type &to) const{
    return replace(from.slice(),to.slice());
  };
  stringT<Alloc> replace(const char*from, const char*to) const{
    return replace(stringview(from),stringview(to));
  };
  stringT<Alloc> replace(const stringview &from, const stringview &to) const;
  stringT<Alloc> replaceAll(const stringview &from, const stringview &to) const;

  static stringT<Alloc> join(const vector<stringT<Alloc>, Alloc> &arr,
                             const stringT<Alloc> &sep);

  void split(const stringT<Alloc> &splitTag,
             tinystl::vector<stringT<Alloc>, Alloc> &eleVec,
             bool trim = false) const;

  void split(const stringview &splitTag,
             tinystl::vector<stringview, Alloc> &eleVec,
             bool trim = false) const;

  static tinystl::vector<stringT<Alloc>> split(const stringT<Alloc> &str,
                                               const stringT<Alloc> &splitTag) {
    tinystl::vector<stringT<Alloc>> ret;
    str.split(splitTag, ret);
    return std::move(ret);
  }

  this_type convertToLowcaseWithSep() const;

  this_type removeQuote() const;

  stringview trim(char what = 0) const;

  void trimSelf(char what = 0) { *this = trim(what); }

  void clear() {
    freeself();
    memset(m_buffer, 0, c_nbuffer);
  }

  bool isFloat() const { return find_first_not_of("+-.0123456789") == npos; }

  bool isInteger() const { return find_first_not_of("-0123456789") == npos; }
  int compare(const stringT<Alloc> &str) const;
  int compare(size_t pos, size_t len, const stringT<Alloc> &str) const;
  int compare(size_t pos, size_t len, const stringT<Alloc> &str, size_t subpos,
              size_t sublen = npos) const;
  int compare(const char *s) const;
  int compare(size_t pos, size_t len, const char *s) const;
  int compare(size_t pos, size_t len, const char *s, size_t n) const;

  size_t rfind(const stringT<Alloc> &str, size_t pos = npos) const;
  size_t rfind(const char *s, size_t pos = npos) const;
  size_t rfind(const char *s, size_t pos, size_t n) const;
  size_t rfind(char c, size_t pos = npos) const;

private:
  typedef char *pointer;
  pointer m_first;
  usize m_size;
  usize m_capacity;

  static const usize c_nbuffer = 8;
  char m_buffer[c_nbuffer];

  void move(stringT<Alloc> &&other);

  void freeself() {
    if (m_first != m_buffer)
      Alloc::static_deallocate(m_first, m_capacity);
    m_first = m_buffer;
    m_size = 0;
    m_capacity = c_nbuffer;
  }
  char &back() const { return *((char *)m_first + m_size); }
  int compare_aux(size_t pos, size_t len, const stringT<Alloc> &cit,
                  size_t subpos, size_t sublen) const;
  size_t rfind_aux(const stringT<Alloc> &cit, size_t pos, size_t lengthOfS,
                   int cond) const;
  size_t changeVarWhenEuqalNPOS(size_t var, size_t minuend, size_t minue) const;
};

template <typename Alloc>
stringT<Alloc> stringT<Alloc>::convertToLowcaseWithSep() const {
  this_type ret;
  usize j = 0;
  for (usize i = 0; i < size(); i++) {
    if (m_first[i] >= 'A' && m_first[i] <= 'Z') {
      ret.append(m_first + j, m_first + i);
      ret.append("-");
      ret.append('a' + m_first[i] - 'A');
      j = i + 1;
    }
  }
  if (j < size())
    ret.append(m_first + j, m_size - j);
  return ret;
}

template <typename Alloc>
stringT<Alloc> stringT<Alloc>::replace(const stringview &from,
                                       const stringview &to) const {
  int pos = find(from);
  if (pos == npos)
    return *this;
  stringT<Alloc> ret;

  if (to.size() > from.size())
    ret.reserve(size() + to.size() - from.size());

  ret.append(m_first, m_first + pos);
  ret.append(to);
  ret.append(m_first + pos + from.size());

  return ret;
}

template <typename Alloc>
stringT<Alloc> stringT<Alloc>::replaceAll(const stringview &from,
                                          const stringview &to) const {
  int pos = find(from);
  if (pos == npos)
    return *this;
  stringT<Alloc> ret;

  int cur = 0;
  do {
    ret += substr(cur, pos - cur);
    ret += to;
    cur = pos + from.size();
    pos = find(from, cur);
  } while (pos != npos);

  // add tail
  if (cur < (int)size())
    ret += substr(cur, size() - cur);

  return ret;
}

template <typename Alloc>
stringT<Alloc> stringT<Alloc>::join(const vector<stringT<Alloc>, Alloc> &arr,
                                    const stringT<Alloc> &sep) {
  if (arr.empty())
    return "";

  stringT<Alloc> ret;

  usize totalLength = 0;
  for (const auto &it : arr)
    totalLength += it.size();
  totalLength += sep.size() * (arr.size() - 1);
  ret.reserve(totalLength);

  auto it = arr.begin();
  ret.append(*it++);
  while (it != arr.end()) {
    ret.append(sep);
    ret.append(*it++);
  };
  return ret;
}

template <typename Alloc> stringT<Alloc> stringT<Alloc>::removeQuote() const {
  if (size() < 2)
    return *this;
  if ((*m_first == '\'' && *(m_first + m_size - 1) == '\'') ||
      (*m_first == '"' && *(m_first + m_size - 1) == '"')) {
    return substr(1, size() - 2);
  }
  return *this;
}

template <typename Alloc>
typename stringT<Alloc>::stringview stringT<Alloc>::trim(char what) const {
  return this->slice().trim(what);
}

template <typename Alloc>
void tinystl::stringT<Alloc>::split(
    const stringT<Alloc> &splitTag,
    tinystl::vector<stringT<Alloc>, Alloc> &eleVec, bool trim) const {
  int curpos = 0;
  for (usize n = 0; n < size(); n++) {
    char ch = (*this)[n];
    if (splitTag.find(ch) != npos) {
      auto r = substr(curpos, n - curpos);
      curpos = n + 1;
      eleVec.push_back(trim ? r.trim() : r);
    }
  }
  // add tail
  if (curpos <= (int)size()) {
    auto r = substr(curpos, size() - curpos);
    eleVec.push_back(trim ? r.trim() : r);
  }
}

template <typename Alloc>
void tinystl::stringT<Alloc>::split(const stringview &splitTag,
                                    tinystl::vector<stringview, Alloc> &eleVec,
                                    bool trim) const {
  int curpos = 0;
  for (usize n = 0; n < size(); n++) {
    char ch = (*this)[n];
    if (splitTag.find(ch) != npos) {
      auto r = substr(curpos, n - curpos);
      curpos = n + 1;
      eleVec.push_back(trim ? r.trim() : r);
    }
  }
  // add tail
  if (curpos <= (int)size()) {
    auto r = substr(curpos, size() - curpos);
    eleVec.push_back(trim ? r.trim() : r);
  }
}

template <typename Alloc>
void tinystl::stringT<Alloc>::replace(char t, char r) {
  for (pointer it = m_first; it != end(); ++it) {
    if (*it == t) {
      *it = r;
    }
  }
}

typedef stringT<TINYSTL_ALLOCATOR> string;

template <typename Alloc> inline stringT<Alloc>::stringT() {
  m_first = m_buffer;
  m_size = 0;
  m_capacity = c_nbuffer;
  resize(0);
}

template <typename Alloc>
inline stringT<Alloc>::stringT(const stringT<Alloc> &other) : stringT() {
  operator=(other);
}

template <typename Alloc>
inline stringT<Alloc>::stringT(stringT<Alloc> &&other) {
  move(std::move(other));
}

template <typename Alloc>
inline void stringT<Alloc>::move(stringT<Alloc> &&other) {
  if (other.m_first != other.m_buffer) {
    m_first = other.m_first;
    m_size = other.m_size;
    m_capacity = other.m_capacity;

    // reset other string to default
    other.m_first = other.m_buffer;
    other.m_size = 0;
    other.m_capacity = c_nbuffer;
  } else {
    memcpy(m_buffer, other.m_buffer, c_nbuffer);
    m_first = m_buffer;
    m_size = other.size();
    m_capacity = c_nbuffer;
  }
}

template <typename Alloc>
inline stringT<Alloc>::stringT(const char *sz) : stringT() {
  if (sz == nullptr)
    sz = "";
  usize len = strlen(sz);
  reserve(len);
  memcpy(m_first, sz, len);
  m_size = len;
  m_first[len] = 0;
}

template <typename Alloc>
stringT<Alloc> stringT<Alloc>::format(const char *msg, ...) {
  va_list ap;
  va_start(ap, msg);
  int length = vsnprintf(NULL, 0, msg, ap);
  if (length <= 0) {
    return nullptr;
  }
  char *p = (char *)alloca(length + 1);
  va_start(ap, msg);
  int res = vsnprintf(p, length + 1, msg, ap);
  va_end(ap);
  if (res <= 0) {
    return nullptr;
  }
  stringT<Alloc> ret(p, length);
  return ret;
}

template <typename Alloc>
inline stringT<Alloc>::stringT(const bx::StringView &view) : stringT() {
  reserve(view.getLength());
  append(view.getPtr(), view.getPtr() + view.getLength());
}

template <typename Alloc>
inline stringT<Alloc>::stringT(const char *sz, usize len) : stringT() {
  reserve(len);
  append(sz, sz + len);
}

template <typename Alloc> stringT<Alloc>::~stringT() { freeself(); }

template <typename Alloc>
inline stringT<Alloc> &stringT<Alloc>::operator=(const stringT<Alloc> &other) {
  if (this == &other)
    return *this;

  if (other.m_first == other.m_buffer) {
    freeself();
    memcpy(m_buffer, other.m_buffer, c_nbuffer);
    m_first = m_buffer;
    m_capacity = c_nbuffer;
  } else {
    reserve(other.size());
    memcpy(m_first, other.m_first, other.size());
  }
  m_size = other.size();
  back() = 0;
  return *this;
}

template <typename Alloc>
inline stringT<Alloc> &stringT<Alloc>::operator=(stringT<Alloc> &&other) {
  freeself();
  move(std::move(other));
  return *this;
}

template <typename Alloc> inline const char *stringT<Alloc>::c_str() const {
  return m_first;
}

template <typename Alloc> inline usize stringT<Alloc>::size() const {
  return m_size;
}

template <typename Alloc> inline bool stringT<Alloc>::empty() const {
  return 0 == m_size;
}

template <typename Alloc> inline void stringT<Alloc>::reserve(usize capacity) {
  if (capacity + 1 <= m_capacity) {
    return;
  }

  const usize _size = m_size;

  pointer newfirst = (pointer)Alloc::static_allocate(capacity + 1);
  if (_size)
    ::memcpy(newfirst, m_first, _size);

  freeself();

  m_first = newfirst;
  m_size = _size;
  m_capacity = capacity;
}

template <typename Alloc> inline void stringT<Alloc>::resize(usize _size) {
  reserve(_size);
  m_size = _size;
  back() = 0;
}

template <typename Alloc>
inline void stringT<Alloc>::set(const char *first, usize len) {
  freeself();
  if (!first || !len)
    return;

  const usize newsize = (usize)((end() - m_first) + len + 1);
  if (newsize >= m_capacity)
    reserve((newsize * 3) / 2);

  ::memcpy(m_first + m_size, first, len);
  m_size += len;
  back() = 0;
}

template <typename Alloc>
inline void stringT<Alloc>::append(const char *first, const char *last) {
  const usize newsize = (usize)(m_size + (last - first) + 1);
  if (newsize >= m_capacity)
    reserve((newsize * 3) / 2);

  const usize len = last - first;
  ::memcpy(m_first + m_size, first, len);
  m_size += len;
  back() = 0;
}

template <typename Alloc>
inline void stringT<Alloc>::append(const char *str, usize len) {
  if (!str)
    return;
  if (!len)
    append(str, str + strlen(str));
  else
    append(str, str + len);
}

template <typename Alloc>
inline void stringT<Alloc>::insert(size_t pos, const char *str) {
  if (!str)
    return;
  assert(pos <= size());
  auto len = strlen(str);
  const usize newsize = (usize)(m_size + len + 1);
  if (newsize >= m_capacity)
    reserve((newsize * 3) / 2);

  ::memmove(m_first + pos + len, m_first + pos, m_size - pos);
  ::memcpy(m_first + pos, str, len);
  m_size += len;
  back() = 0;
}

template <typename Alloc> void stringT<Alloc>::lower() {
  auto lit = const_cast<char *>(c_str());
  auto lend = lit + size();
  while (lit != lend) {
    *lit = tolower(*lit);
    lit++;
  }
}

template <typename Alloc> void stringT<Alloc>::upper() {
  auto lit = const_cast<char *>(c_str());
  auto lend = lit + size();
  while (lit != lend) {
    *lit = toupper(*lit);
    lit++;
  }
}

template <typename Alloc> stringT<Alloc> stringT<Alloc>::toUpperCase() {
  auto lit = const_cast<char *>(c_str());
  usize length = size();

  stringT<Alloc> upperStr;
  char *upperArray = new char[length];

  for (usize i = 0; i < length; i++) {
    *(upperArray + i) = toupper(*lit);
    lit++;
  }

  upperStr.append(upperArray, upperArray + length);
  delete[] upperArray;
  return upperStr;
}

template <typename Alloc> stringT<Alloc> stringT<Alloc>::toLowerCase() {
  auto lit = const_cast<char *>(c_str());
  usize length = size();

  stringT<Alloc> lowerStr;
  char *lowerArray = new char[length];
  for (usize i = 0; i < length; i++) {
    *(lowerArray + i) = tolower(*lit);
    lit++;
  }

  lowerStr.append(lowerArray, lowerArray + length);
  delete[] lowerArray;
  return lowerStr;
}

template <typename Alloc>
stringT<Alloc> stringT<Alloc>::itos(int value, int base) {
  BX_CHECK(base != 1 && base <= 36 && base >= 0,
           "terminating with uncaught exception of type invalid_argument: "
           "itos: no conversion");

  base = base == 0 ? 10 : base;
  char index[] = "0123456789abcdefghijklmnopqrstuvwxyz";
  int length = 0;
  unsigned int unsignedValue = value;
  stringT<Alloc> str = "";

  if (value < 0) {
    unsignedValue = abs(value);
    str.append('-');
    length++;
  }

  // Use do-while to deal with the input number is 0
  do {
    str.append(index[unsignedValue % base]);
    unsignedValue /= base;
    length++;
  } while (unsignedValue);

  char *strPtr = (char *)str.c_str();
  // if number is negative the revert index begin with 1
  int beginIdx = strPtr[0] == '-' ? 1 : 0;

  for (int i = beginIdx; i <= (length - 1) / 2; i++) {
    int step = i - beginIdx;
    int tailIdx = (length - 1) - step;

    char temp = strPtr[i];
    strPtr[i] = strPtr[tailIdx];
    strPtr[tailIdx] = temp;
  }

  return str;
}

template <typename Alloc>
int stringT<Alloc>::stoi(const stringT<Alloc> &str, usize *idx, int base) {
  BX_CHECK(base != 1 && base <= 36 && base >= 0,
           "terminating with uncaught exception of type invalid_argument: "
           "stoi: no conversion");

  int num = 0;
  int pos = 0;
  int sign = '+';
  base = base == 0 ? 10 : base;

  str.lower();
  const char *digit = str.c_str();

  // Remove WhiteSpace of string before convert
  while (isspace(*digit)) {
    digit++;
    pos++;
  }

  // Get Sign of the number, if number do not have negative sign,
  // using positive sign as default sign
  if (*digit == '+' || *digit == '-') {
    sign = *digit;
    digit++;
    pos++;
  }

  // BX_CHECK(isValidDigit(*digit, base), "string convert is out of range ");

  while (*digit != '\0') {
    if (isValidDigit(*digit, base)) {
      char temp = *digit >= 'a' ? *digit - 'a' + 10 : *digit - '0';
      num = num * base + temp;
      digit++;
      pos++;
    } else {
      break;
    }
  }

  if (idx)
    *idx = pos;
  if (sign == '-')
    return -num;

  return num;
}

template <typename Alloc>
bool stringT<Alloc>::beginWith(const stringT<Alloc> &prefix) const {
  if (prefix.size() > this->size())
    return false;

  auto lit = prefix.c_str(), rit = this->c_str();
  auto lend = lit + prefix.size();
  while (lit != lend) {
    if (*lit++ != *rit++)
      return false;
  }

  return true;
}

template <typename Alloc>
bool stringT<Alloc>::endWith(const stringT<Alloc> &suffix) const {
  if (suffix.size() > this->size())
    return false;

  auto lit = suffix.c_str(), rit = this->c_str() + this->size() - suffix.size();
  auto lend = lit + suffix.size();
  while (lit != lend) {
    if (*lit++ != *rit++)
      return false;
  }

  return true;
}

template <typename Alloc>
typename stringT<Alloc>::stringview stringT<Alloc>::substr(usize from,
                                                           int len) const {
  if (from >= size())
    return stringview();
  if (len < 0 || from + len > size())
    len = (int)(size() - from);
  return stringview(data() + from, len);
}

template <typename Alloc>
inline bool operator==(const stringT<Alloc> &lhs, const stringT<Alloc> &rhs) {
  return strcmp(lhs.c_str(), rhs.c_str()) == 0;
}

template <typename Alloc>
inline bool operator!=(const stringT<Alloc> &lhs, const stringT<Alloc> &rhs) {
  return strcmp(lhs.c_str(), rhs.c_str()) != 0;
}

template <typename Alloc>
inline bool operator==(const stringT<Alloc> &lhs, const char *rhs) {
  if (rhs == nullptr)
    rhs = "";
  return strcmp(lhs.c_str(), rhs) == 0;
}

template <typename Alloc>
inline bool operator==(const typename stringT<Alloc>::stringview &lhs,
                       const stringT<Alloc> &rhs) {
  usize sz = bx::min(lhs.size(), rhs.size());
  return strncmp(lhs.data(), rhs.data(), sz) == 0;
}

template <typename Alloc>
inline bool operator==(const stringT<Alloc> &lhs,
                       const typename stringT<Alloc>::stringview &rhs) {
  usize sz = bx::min(lhs.size(), rhs.size());
  return strncmp(lhs.data(), rhs.data(), sz) == 0;
}

template <typename Alloc>
inline bool operator==(const typename stringT<Alloc>::stringview &lhs,
                       const typename stringT<Alloc>::stringview &rhs) {
  usize sz = bx::min(lhs.size(), rhs.size());
  return strncmp(lhs.data(), rhs.data(), sz) == 0;
}

template <typename Alloc>
inline bool operator==(const char *lhs, const stringT<Alloc> &rhs) {
  return rhs == lhs;
}

template <typename Alloc>
inline bool operator!=(const stringT<Alloc> &lhs, const char *rhs) {
  return !(lhs == rhs);
}

template <typename Alloc>
static inline usize hash(const stringT<Alloc> &value) {
  return hash_string(value.c_str(), value.size());
}

// siney
template <typename Alloc>
stringT<Alloc> stringT<Alloc>::operator+(const stringT<Alloc> &rhs) const {
  stringT<Alloc> ret(*this);
  ret.append(rhs.c_str(), rhs.c_str() + rhs.size());
  return std::move(ret);
}

// siney
template <typename Alloc>
stringT<Alloc> operator+(const char *lhs, const stringT<Alloc> &rhs) {
  stringT<Alloc> ret(lhs);
  ret.append(rhs.c_str(), rhs.c_str() + rhs.size());
  return std::move(ret);
}

// siney
template <typename Alloc>
stringT<Alloc> operator+(const typename stringT<Alloc>::stringview &lhs,
                         const stringT<Alloc> &rhs) {
  stringT<Alloc> ret(lhs);
  ret.append(rhs);
  return std::move(ret);
}

// siney
template <typename Alloc>
void stringT<Alloc>::operator+=(const stringT<Alloc> &rhs) {
  append(rhs.c_str(), rhs.c_str() + rhs.size());
}

template <typename Alloc>
void stringT<Alloc>::pathConcat(const stringT<Alloc> &rhs) {
  if (!endWith("/") && !endWith("\\"))
    append("/");
  if (rhs.beginWith("./")) // skip current path "./"
    append(rhs.c_str() + 2, rhs.c_str() + rhs.size());
  else
    append(rhs.c_str(), rhs.c_str() + rhs.size());
}

template <typename Alloc>
void stringT<Alloc>::pathConcat(const stringview &rhs) {
  if (!endWith("/") && !endWith("\\"))
    append("/");
  if (rhs.beginWith("./")) // skip current path "./"
    append(rhs.substr(2));
  else
    append(rhs);
}

// siney, concat 2 path
template <typename Alloc>
stringT<Alloc> stringT<Alloc>::operator/(const stringT<Alloc> &rhs) const {
  stringT<Alloc> ret(*this);
  ret.pathConcat(rhs);
  return std::move(ret);
}

// siney, concat 2 path
template <typename Alloc>
stringT<Alloc> operator/(const char *lhs, const stringT<Alloc> &rhs) {
  stringT<Alloc> ret(lhs);
  ret.pathConcat(rhs);
  return std::move(ret);
}

// template <typename Alloc>
// stringT<Alloc> operator+(typename stringT<Alloc>::stringview& lhs, const
// char* rhs) {
//  stringT<Alloc> ret(lhs);
//  ret.append(rhs);
//  return std::move(ret);
//}

// kidd
template <typename Alloc>
inline bool operator<(const stringT<Alloc> &lhs, const stringT<Alloc> &rhs) {
  return strcmp(lhs.c_str(), rhs.c_str()) < 0;
}

template <typename Alloc>
int stringT<Alloc>::findLast(const stringT<Alloc> &str) const {
  if (str.size() > size() || str.empty() || empty())
    return npos;
  for (int i = str.size(); i <= (int)size(); i++) {
    const char *where = strstr(c_str() + size() - i, str.c_str());
    if (!where)
      continue;
    return (int)(where - c_str());
  }
  return npos;
}

template <typename Alloc>
int stringT<Alloc>::findNot(const stringT<Alloc> &str, usize pos) const {
  for (int n = pos; n < size(); n++) {
    auto ch = (*this)[n];
    if ((str.find(ch)) == npos)
      return n;
  }
  return npos;
}

template <typename Alloc>
int stringT<Alloc>::compare(const stringT<Alloc> &str) const {
  return compare(0, size(), str, 0, str.size());
}

template <typename Alloc>
int stringT<Alloc>::compare(size_t pos, size_t len,
                            const stringT<Alloc> &str) const {
  return compare(pos, len, str, 0, str.size());
}

template <typename Alloc>
int stringT<Alloc>::compare_aux(size_t pos, size_t len,
                                const stringT<Alloc> &cit, size_t subpos,
                                size_t sublen) const {
  size_t i, j;
  for (i = 0, j = 0; i != len && j != sublen; ++i, ++j) {
    if ((*this)[pos + i] < cit[subpos + j])
      return -1;
    else if ((*this)[pos + i] > cit[subpos + j])
      return 1;
  }
  if (i == len && j == sublen)
    return 0;
  else if (i == len)
    return -1;
  else
    return 1;
}

template <typename Alloc>
int stringT<Alloc>::compare(size_t pos, size_t len, const stringT<Alloc> &str,
                            size_t subpos, size_t sublen) const {
  return compare_aux(pos, len, str.begin(), subpos, sublen);
}

template <typename Alloc> int stringT<Alloc>::compare(const char *s) const {
  return compare(0, size(), s, strlen(s));
}

template <typename Alloc>
int stringT<Alloc>::compare(size_t pos, size_t len, const char *s) const {
  return compare(pos, len, s, strlen(s));
}

template <typename Alloc>
int stringT<Alloc>::compare(size_t pos, size_t len, const char *s,
                            size_t n) const {
  return compare_aux(pos, len, s, 0, n);
}

// 反向查找
template <typename Alloc>
size_t stringT<Alloc>::rfind_aux(const stringT<Alloc> &cit, size_t pos,
                                 size_t lengthOfS, int cond) const {
  int i, j;
  for (i = pos + lengthOfS; i >= cond; --i) {
    for (j = 0; j != lengthOfS; ++j) {
      if (*(begin() + i + j) != cit[j])
        break;
    }
    if (j == lengthOfS)
      return i;
  }
  return npos;
}

template <typename Alloc>
size_t stringT<Alloc>::rfind(const stringT<Alloc> &str, size_t pos) const {
  auto lengthOfS = str.size();
  pos = changeVarWhenEuqalNPOS(pos, size(), 1);
  return rfind_aux(str.begin(), pos, lengthOfS, 0);
}

template <typename Alloc>
size_t stringT<Alloc>::rfind(const char *s, size_t pos) const {
  pos = changeVarWhenEuqalNPOS(pos, size(), 1);
  return rfind(s, pos, strlen(s));
}

template <typename Alloc>
size_t stringT<Alloc>::rfind(const char *s, size_t pos, size_t n) const {
  auto lengthOfS = strlen(s);
  return rfind_aux(s, pos, n, 0);
}

template <typename Alloc>
inline size_t stringT<Alloc>::changeVarWhenEuqalNPOS(size_t var, size_t minuend,
                                                     size_t minue) const {
  return (var == npos ? minuend - minue : var);
}

} // namespace tinystl
#endif
